This invention relates to a packet forwarding device which includes a high-speed routing table search unit, and more particularly to a packet forwarding device which realizes a high speed of routing table search by using a CAM.
A router that constitutes an Internet Protocol (IP) network judges an IP address (next hop IP address) of a forwarding destination network device from a destination IP address of an input packet, and forwards the packet to an output line which reaches the network device.
To judge the next hop IP address, the router includes a routing table for storing a plurality of routing entries containing prefixes which are IP address high order bits and indicate networks, and next hop IP addresses corresponding to the prefixes. Upon the input of the packet, the router searches for a routing entry in which the prefix of each entry matches high order bits of a destination IP address in a header, and judges a next hop IP address in the matched routing entry to be a next hop IP address of the input packet.
When a plurality of routing entries match, a routing entry in which a bit length of a prefix (prefix length) is longer is judged to be a matched routing entry. Hereinafter, a series of these judging operations will be referred to as routing table search.
The routing table search will specifically be described by using a routing table shown in FIG. 13. FIG. 13 shows a case in which there are six routing entries 1101-1 to 1101-6 in a routing table 1100 when an. IP address is represented by 8 bits. Each routing entry 1101 includes an IP address condition which is information equivalent to a prefix, and a next hop IP address which corresponds to each IP address condition. The IP address condition is information in which a prefix is represented by high order bits and remaining bits of an IP address are represented as a mask (*).
For example, consideration will be given to a case in which a packet of a destination IP address represented by a binary number “00010100” is input to the router. In routing table search in this case, IP address conditions and IP destination addresses of the routing entries 1101-1 and 1101-4 match each other, but a next hop IP address: A in the routing entry 1101-1 in which a prefix length is longer is judged to be a next hop IP address of the input packet.
To realize a high speed of the routing table search, there has been presented a routing table search method which uses a Ternary Contents Addressable Memory (TCAM) as a high-speed searching device. For example, “Flow Identification Method Using Content Addressable Memory (CAM)”, by MASANORI Uga, KOHEI Shiohira, p. 654, SB-4-2, 2000 General Convention Lecture Collected Papers, Institute of Electronics, Information and Communication Engineers, (hereinafter, referred to as “Nonpatent Document 1”) describes a method of realizing routing table search and a flow identification process by the TCAM at a high speed.
The TCAM includes a plurality of entries which store a plurality of bits of matching conditions, executes match comparison between a search key and matching conditions in the entries upon an input of the search key, and outputs a smallest address value among addresses of the matched entries at a high speed. Moreover, according to the TCAM, it is possible to designate not only “0” or “1” for each bit of a matching condition but also a mask (“*”) which indicates that a search key may be either “0” or “1”.
The routing table searching method of the Nonpatent Document 1 includes a TCAM which stores IP address conditions of routing entries in long order of prefix lengths, and a search result table which stores next hop IP addresses corresponding to the IP address conditions.
A mask part of the IP address condition corresponds to a mask of the TCAM. According to the routing table searching method, upon an input of a packet, a destination IP address in a packet header is input as a search key to the TCAM included therein. The TCAM compares the search key with the set IP address conditions, and judges a smallest address among addresses in which matched IP address conditions are stored. The routing table searching method judges a next hop IP address of the search result table corresponding to the address, to be a next hop IP address of the input packet. The TCAM can perform high-speed search irrespective of the number of set entries, i.e., the number of IP address conditions.
Referring to a conceptual diagram of FIG. 14, a routing table search unit to which the Nonpatent Document 1 is applied will be described. The routing table search unit of FIG. 14 includes a TCAM 1200 in which the IP address conditions of the six routing entries shown in FIG. 13 are set as IP address conditions 1201-i in order of prefix lengths, and a search result table 1210 which stores next hop IP addresses corresponding to the IP address conditions 1201-i (i=1 to 6) as next hop IP addresses 1211-i (i=1 to 6).
For example, when a packet of a destination IP address “00010101” is input, the TCAM 1200 of the routing table search unit compares the destination IP address with the IP address conditions 1201-i, and outputs a smallest address “2” among matched IP address conditions 1201.
The routing table search unit judges a next hop IP address: B corresponding to the address “2” of the search result table 1210 to be a next hop IP address of the input packet.
However, in realization of a high speed of the routing table searching method which uses the TCAM, search performance of the TCAM first becomes a bottleneck.
Additionally, when the routing table search unit includes a TCAM and a CAM control device such as an ASIC or a network processor, an input bandwidth of a search key between the TCAM and the CAM control device becomes a bottleneck.
According to the Nonpatent Document 1, since all the bits of the destination address of the received packet are always input as a search key to the TCAM, an input bandwidth of the search key is consumed to a maximum. Furthermore, since the TCAM executes match comparison of the long search key with the entries therein, search resources are consumed to a maximum. Accordingly, there is a problem in that when the search performance of the TCAM or the input bandwidth of the search key between the TCAM and the CAM control device becomes a bottleneck, only worst search performance is realized.
As a routing table searching method that eliminates the bottleneck of the CAM search performance, there has been known a technique disclosed in JP 2000-358064A which uses a plurality of CAMs. According to JP 2000-358064 A, routing table search is carried out in two stages. The first search is executed at a unit of the first stage by using a Contents Addressable Memory (CAM), and the second search is executed by arranging a tree at a unit of the second stage. The unit of the first stage includes a CAM for each group based on a prefix length of a routing entry. Only bits of a shortest prefix length in the routing entries of each group are stored in the CAM. At the time of search, bits of a destination IP address corresponding to bits set in each CAM are input, and the CAM outputs an address of a tree-stored memory corresponding to a matched entry. The unit of the second stage executes tree search based on the address, and decides a next hop IP address.